import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=493 lang=java
 *
 * [493] 翻转对
 */

// @lc code=start
class Solution {

    public int mergeSort(int[] arr, int lo, int hi) {

        if (hi <= lo) return 0;
        int mid = lo + (hi - lo) / 2;

        int cnt = mergeSort(arr, lo, mid) + mergeSort(arr, mid + 1, hi);

        for (int i = lo, j = mid + 1; i <= mid; i++) {
            while ( j <= hi &&arr[i]/2.0 > arr[j]) {
                j++;
            }
            cnt += j - (mid + 1);
        }
        
        Arrays.sort(arr, lo, hi + 1);
        return cnt;
    }

    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
}
// @lc code=end

